Wireless networks have experienced increased development in the past decade. Two types of wireless networks are infra-structure based wireless networks, and ad hoc wireless networks.
An infra-structure based wireless network typically includes a communication network with fixed and wired gateways. Many infra-structure based wireless networks employ a mobile unit or host which communicates with a fixed base station that is coupled to a wired network. The mobile unit can move geographically while it is communicating over a wireless link to the base station. When the mobile unit moves out of range of one base station, it may connect or “handover” to a new base station and start communicating with the wired network through the new base station.
In comparison to infra-structure based wireless networks, such as cellular networks or satellite networks, ad hoc networks are self-forming networks which can operate in the absence of any fixed infrastructure, and in some cases the ad hoc network is formed only of mobile nodes. An ad hoc network typically includes a number of geographically-distributed, potentially mobile units, some times referred to as “nodes” which are wirelessly connected to each other by one or more links (e.g., radio frequency channels). The nodes can communicate with each other over a wireless media without the support of an infra-structure based or wired network. Ad hoc networks are also self-healing. Links or connections between these nodes can change dynamically in an arbitrary manner as existing nodes move within the ad hoc network, as new nodes join or enter the ad hoc network, or as existing nodes leave or exit the ad hoc network. Because the topology of an ad hoc network can change significantly techniques are needed which can allow the ad hoc network to dynamically adjust to these changes. Due to the lack of a central controller, many network-controlling functions can be distributed among the nodes such that the nodes can self-organize and reconfigure in response to topology changes.
One characteristic of the nodes is that their transmission range is usually relatively limited in comparison to cellular networks. Each node can typically communicate directly over a short range with nodes which are a single “hop” away. Such nodes are sometimes referred to as “neighbor nodes.” When a node transmits packets to a destination node and the nodes are separated by more than one hop (e.g., the distance between two nodes exceeds the radio transmission range of the nodes, or a physical barrier is present between the nodes), the packets can be relayed via intermediate nodes (“hop-by-hop”) until the packets reach the destination node. Each intermediate node acts as a router which can intelligently route the packets (e.g., data and control information) to another node until the packets eventually reach their final destination. To assist with relaying of packets, each node may maintain routes or routing information to other nodes in the network and can utilize routing techniques to adapt to changes in the interconnectivity between nodes. The nodes can maintain this routing information by performing periodic link and topology updates. Alternatively, nodes may discover routing information only when needed, instead of utilizing updates to maintain routes.
Broadcasting in an ad hoc network relies on nodes to repeat a broadcast until all nodes have received the broadcast message. To avoid excessive broadcast traffic, each node receiving a broadcast message determines if it should rebroadcast the message. For example, a message received more than once by a node should not be rebroadcast by the node. It is desirable to minimize the number of broadcast messages while also ensuring reliable broadcast (e.g., every node will receive each broadcast message). One approach to transmitting broadcast messages in an ad hoc network is known as “flooding.”
FIG. 1 is a block diagram of an ad hoc communication network 100 operating in an infrastructured mode in which a wireless network is created between a plurality of nodes 120A-120O each having wireless repeater and routing capability, and in which three of the nodes 120G, 120L, and 120N are wired Access Points (APs) 130. The ad hoc communication network 100 can implement routing intelligence, which is typically distributed among nodes 120A-120O among APs 130, to help eliminate bottlenecks and improve overall network performance. If access to a wired network is desired, nodes 120A-120O can hop to an AP (typically to the AP that is closest, but to an alternate AP if their current AP is congested or fails). This wireless backhaul mesh can reduce system backhaul costs while increasing network coverage and reliability. It should be appreciated that while the ad hoc network 100 in FIG. 1 is shown as operating with wired APs, the ad hoc network 100 of FIG. 1 does not require any wired network to be present. Rather, the nodes 120A-120O can support peer-to-peer communication without the need for wired infrastructure or other networks.
In the ad hoc network 100, communications to or from nodes 120A-120O can “hop” through each other to reach other nodes 120A-120O in the network. The nodes 120A-120O comprise any wireless devices capable of receiving, transmitting and relaying packetized audio, video and/or data information to another node. Some of the components in an exemplary node, such as an appropriate processor, transmitter, receiver and antenna, are described below. Nodes in close proximity to the APs 130 can receive transmissions from other nodes utilizing the ad hoc air interface and relay these transmissions to infrastructure equipment via uplink communication signal utilizing a cellular, BLUETOOTH or WLAN air interface. Similarly, nodes in close proximity to the APs 130 can receive downlink communications over the cellular, BLUETOOTH or WLAN air interface and transmit uplink communications to another node via the ad hoc air interface. In FIG. 4, it is assumed that node A 120A will eventually transmit a broadcast packet or message using a relay approach, but that relay nodes have not yet been selected. The nodes 120A-120O can communicate information packets over wireless carrier frequencies, each of which includes one or more wireless communication channels depending on the multiple access scheme utilized in the network 100.
The access points 130 are typically coupled to a wired network (not shown) and can provide one or more sources of audio, video and/or data information. The access points 130 may be a cellular base station, a wireless local area network (WLAN) access points such as those complying with the IEEE 802.11 standard, or may also be a Bluetooth access point or the like. Although not shown in FIG. 1, it should be appreciated that the nodes 120A-120O, can also communicate information packets with a cellular-based network (not shown) over wireless carrier frequencies, each of which includes one or more wireless communication channels depending on the multiple access scheme utilized in the cellular-based network. Examples of multiple access schemes which can be used in the network can include any one or more of time division multiple access (TDMA), direct sequence or frequency hopping code division multiple access (CDMA), frequency division multiple access (FDMA), orthogonal frequency division multiplexing (OFDM), opportunity driven multiple access (ODMA), a combination of any of the foregoing multiple access technologies, a multiple access technology in which portions of the frequency spectrum to be used are determined by local signal quality measurements and in which multiple portions of the frequency spectrum may be used simultaneously, or any other multiple access or multiplexing methodology or combination thereof.
FIG. 1 illustrates a “flooding” approach for broadcasting a broadcast packet from node A 120A to other nodes 120B-120O in the ad hoc network. Each node 102A-120O may advertise its presence by periodically broadcasting for an advertisement message. In response to the advertisement message, other nodes within range may acknowledge their presence by identifying themselves. In turn, each node may identify its neighbor nodes, and maintain a neighbor list of nodes in proximity to that node. As used herein, a “neighbor node” is a node which is one hop away from the node such that the nodes may communicate with each other. At the particular instant in time shown in FIG. 1, node D 120D, for example, has four neighbor nodes—node C 120C, node E 120E, node G 120G, and node H 120H. A particular node's neighbor list changes dynamically as the topology of the network changes.
According to this “flooding” approach, each node initially receiving the broadcast packet from node A 120A acts as a “repeater” node (indicated by the dashed-line circle) that transmits the broadcast packet to all of its neighbor nodes. This process continues until all nodes have received the broadcast packet. For example, when a node B 120B receives a packet, node B 120B determines whether the received packet is a broadcast packet. If the received packet is a unicast packet, then node B 120B transmits the packet to the neighboring node it is addressed to or intended for. If the received packet is a broadcast packet, then node B 120B transmits the received broadcast packet to each of its neighbor nodes. In this exemplary topology, node B 120B transmits the broadcast packet received from node A 120A to its neighbor nodes, Node C 120C and Node E 120E. At the same time, node C 120C transmits the broadcast packet received from node A 120A to its neighbor nodes Node B 120B, Node D 120D, and Node G 120G. To continue propagating the broadcast packet through the network 110, Node D 120D, Node E 120E and Node G 120G (e.g., the nodes receiving the broadcast packet from the repeater nodes Node B 120B, Node C 120C), then serve as a repeater node (indicated by the dashed-line circle) that transmits the broadcast packet to all of its neighbor nodes. For example, Node D 120D would transmit the broadcast packet to each of its four neighbor nodes—node C 120C, node E 120E, node G 120G, and node H 120H. Thus, broadcast packet transmission via flooding can potentially raise the reliability of transmission since a given node's probability of receiving the broadcast packet from at least node tends to be relatively high.
However, in many network topologies, the same node is likely to receive and/or transmit the same broadcast packet more than once. For example, after initially receiving the broadcast packet from node A 120A, node C 120C would receive it at least two more times from node B 120B and node D 120D and possibly also from node G 120G. Thus, using the flooding approach to broadcast packets can generate excessive amounts of system traffic which can unnecessarily consume bandwidth since the same data is redundantly received and/or transmitted. This approach can also increase the probability of channel congestion, overload and/or interference in the ad hoc network since each node transmits the broadcast packet to its neighbor nodes upon receipt. As a result, the likelihood of packet collisions increases since some nodes overlap but do not have mechanisms (e.g., centralized controller) for adjusting the timing in overlapping transmission areas. In addition, signaling messages greatly increase since every node rebroadcasts the broadcast packets. Moreover, flooding methods are not scalable.
A number of alternatives to the flooding method have been proposed for broadcasting in ad hoc networks. One approach is to elect a subset of relay nodes that form a backbone network for relaying broadcast messages. However, in high mobility ad hoc networks these techniques can be inefficient due to the high frequency at which links between nodes tend to break and the rapidity of other topology changes.
According to another approach, the probability of retransmission is modified based on local density of the network. According to yet another approach, receiving nodes utilize predetermined criterion to decide whether to retransmit the received information. According to still another approach, location is used to optimize broadcasts; each node transmits its location with the broadcast message and other nodes calculate their distance from the source or relay node in order to decide whether to rebroadcast.
Notwithstanding these advances, it would be desirable to provide broadcast protocols for use in ad hoc networks which exhibit improved broadcast efficiency. For example, it would be desirable to provide techniques which can make the transmission more orderly and thereby reduce the number of redundant broadcast packets a given node receives. It would also be desirable to provide techniques that can reduce the likelihood of broadcast packet collisions. It would also be desirable to provide techniques for dynamically relaying broadcast messages throughout an ad hoc network while minimizing the number of relay transmissions.
Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.